package com.leetcode.binary_search;

/**
 * @author Dennis Li
 * @date 2020/7/24 16:42
 */
public class NextGreatestLetter_744 {

    public char nextGreatestLetter(char[] letters, char target) {
        int n = letters.length - 1;
        // 超界，返回第一个字符
        if (letters[n] <= target || letters[0] > target) return letters[0];
        int i = 0, j = n;
        while (i < j) {
            // 防止相加超界
            int mid = i + (j - i) >> 1;
            if (letters[mid] <= target) {
                if (letters[mid + 1] > target) return letters[mid + 1];
                i = mid + 1;
            } else {
                if (letters[mid - 1] <= target) return letters[mid];
                j = mid - 1;
            }
        }
        return letters[0];
    }

    public char nextGreatestLetter2(char[] letters, char target) {
        // 超界，返回第一个字符
        int n = letters.length - 1;
        int i = 0, j = n;
        while (i <= j) {
            // 防止相加超界
            int mid = i + (j - i) >> 1;
            if (letters[mid] <= target)
                // 相等时也不需要返回
                i = mid + 1;
            else
                j = mid - 1;
        }
        // 没有超界返回i处的值，超界则返回序号0处的值
        return i < n ? letters[i] : letters[0];
    }

}
